package lanQiaoBei.tree;

import sjjg.tree.BinaryTree;

import java.util.LinkedList;
import java.util.Stack;

public class TreeErgodic {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.setLeft(node6);
        node1.setRight(node7);
        node6.setLeft(node3);
        node6.setRight(node2);
        node7.setLeft(node4);
        node7.setRight(node5);
        System.out.print("前序遍历->");
        preOrderRecur(node1);
        System.out.println();
        System.out.print("中序遍历->");
        midOrderRecur(node1);
        System.out.println();
        System.out.print("后序遍历->");
        aftOrderRecur(node1);
        System.out.println();
        System.out.print("基于栈的前序遍历->");
        preOrderRecur(node1);
        System.out.println();
        System.out.print("基于栈的后序遍历->");
        aftOrderStack(node1);
        System.out.println();
        System.out.print("基于栈的中序遍历->");
        midOrderStack(node1);
        System.out.println();
        System.out.print("基于队列的宽度优先遍历->");
        widthFirstOrder(node1);
    }
    /*基于栈的遍历*/
   // 宽度优先遍历
    static void widthFirstOrder(TreeNode root) {
        if (root == null) return;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        while (!queue.isEmpty()) {
            TreeNode removeLast = queue.removeLast();
            System.out.print(removeLast+" ");
            if(removeLast.getLeft()!=null){
                queue.addFirst(removeLast.getLeft());
            }
            if(removeLast.getRight()!=null){
                queue.addFirst(removeLast.getRight());
            }
        }
    }
    //后序遍历 基于自定义栈
    public static void midOrderStack(TreeNode root){
        if(root==null)return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||root!=null){
              if(root!=null){
                  stack.push(root);
                  root=root.getLeft();
              }else {
                  TreeNode pop = stack.pop();
                  System.out.print(pop+" ");
                  root=pop.getRight();
              }
        }
    }
    //后序遍历 基于自定义栈
   static void aftOrderStack(TreeNode root){
        if(root==null)return;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        Stack<TreeNode> collectStack = new Stack<>();
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            collectStack.push(pop);
            if(pop.getLeft()!=null){
                stack.push(pop.getLeft());
            }
            if(pop.getRight()!=null){
                stack.push(pop.getRight());
            }
        }
        while (!collectStack.isEmpty()){
            System.out.print(collectStack.pop()+" ");
        }
    }
    //后序遍历 基于自定义栈
    /*1从栈中弹出一个节点
    * 2打印该弹出节点
    * 3先右后左入栈(如果有的话)
    * 4循环
    * */
    void preOrderStack(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.print( pop+ " ");
            if (pop.getRight() != null) {
                stack.push(root.getRight());
            }
            if (pop.getLeft() != null) {
                stack.push(root.getLeft());
            }
        }
    }

    /*递归遍历*/
    //后序遍历 基于递归序
    static void aftOrderRecur(TreeNode root) {
        if (root == null) return;
        aftOrderRecur(root.getLeft());
        aftOrderRecur(root.getRight());
        System.out.print(root + " ");
    }

    //中序遍历 基于递归序
    static void midOrderRecur(TreeNode root) {
        if (root == null) return;
        midOrderRecur(root.getLeft());
        System.out.print(root + " ");
        midOrderRecur(root.getRight());
    }

    //先序遍历 基于递归序
    static void preOrderRecur(TreeNode root) {
        if (root == null) return;
        System.out.print(root + " ");
        preOrderRecur(root.getLeft());
        preOrderRecur(root.getRight());
    }
}
